EVENTO
Cadeias de Markov Quânticas em Multigrafos Bipartidos
Tipo de evento: Seminário de Avaliação - Série A
Passeios quânticos são uma ferramenta poderosa para obter algoritmos mais eficientes. Esse trabalho apresenta um algoritmo de busca quântico em multigrafos bipartidos, obtendo uma aceleração quadrática em relação a métodos clássicos de busca baseados em cadeias de Markov. A abordagem emprega uma versão adaptada do modelo de passeio quântico de Szegedy, que ocorre nas arestas de grafosbipartidos, e uma versão adaptada dos passeios quânticos escalonados, que ocorrem nos vértices do grafo de linha de multigrafos bipartidos, com o objetivo de encontrar eficientemente um vértice marcado consultando um oráculo. O algoritmo de Ambainis, Gilyén, Jeffery e Kokainis, que proporciona uma aceleração quadrática em grafos bipartidos balanceados, é utilizado como uma sub-rotina doalgoritmo proposto. A abordagem generaliza técnicas existentes de passeios quânticos e oferece uma aceleração quadrática no número de consultas necessárias, demonstrando a utilidade dos modelos propostos em uma classe mais ampla de grafos.Para assistir acesse:meet.google.com/dxx-uozf-mtx
Data Início: 04/04/2025 Hora: 09:00 Data Fim: 04/04/2025 Hora: 12:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Virtual
Aluno: Gustavo Alves Bezerra - - LNCC
Orientador: Andris Ambainis - - Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Carlos Felipe Lardizabal - Universidade Federal do Rio Grande do Sul - UFRGS Marcos Garcia Todorov - Laboratório Nacional de Computação Científica - LNCC Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Suplente Banca Examinadora: Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC